﻿using Algorithm.Struct;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm.SortAlgorithm
{
    public class Optimal_BST
    {
        /// <summary>
        /// 最优二叉树查找树
        /// </summary>
        /// <param name="keyp"></param>
        /// <param name="nullq"></param>
        /// <returns></returns>
        public static int[,] GetBST(double[] keyp, double[] nullq)
        {
            var length = keyp.Length;

            double[,] e = new double[length + 2, length+1];// 期望代价矩阵
            double[,] w = new double[length +2,length+1]; // 概率和

            int[,] root = new int[length, length];// 结果矩阵

            for (int i = 1; i <= length +1; i++)
            {
                e[i, i - 1] = nullq[i - 1];// 初始化 期望代价
                w[i, i - 1] = nullq[i - 1];// 初始化 概率和
            }

            for (int len = 1; len <= length; len++)// len 为长度变量
            {
                for (int i = 1; i <= length - len + 1; i++) // i 为起始点
                {
                    var j = i + len - 1;// j 为某个长为len 的段的终点标号
                    e[i, j] = double.MaxValue;
                    w[i, j] = w[i, j - 1] + keyp[j-1] + nullq[j];
                    for (int r = i; r <= j; r++)
                    {
                        var t = e[i, r - 1] + e[r + 1, j] + w[i, j];
                        if (t < e[i, j])
                        {
                            e[i, j] = t;
                            root[i-1, j-1] = r-1;
                        }
                    }
                }
            }

            return root;
        }

        public static TreeNode<T> CreateSearchBTreeNodeBy<T>(T[] t, int[,] root,int start,int end) where T : IComparable<T>, IEquatable<T>
        {
            if (start > end)
            {
                return null;
            }
            var index = root[start, end];
            var result = new TreeNode<T>(t[index]);
            result.LeftNode = CreateSearchBTreeNodeBy<T>(t, root, start, index-1);
            result.RightNode = CreateSearchBTreeNodeBy<T>(t, root, index + 1, end);
            return result;
        }

        public static SearchBTree<T> CreateSearchBTree<T>(T[] t, int[,] root) where T : IComparable<T>, IEquatable<T>
        {
            return new SearchBTree<T>(CreateSearchBTreeNodeBy<T>(t, root, 0, t.Length - 1));
        }

        public static SearchBTree<T> CreateSearchBTreeByArray<T>(T[] t, double[] keyp, double[] nullq)where T : IComparable<T>, IEquatable<T>
        {
            var root = GetBST(keyp, nullq);
            return CreateSearchBTree<T>(t, root);
        }
    }
}
